import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
 * <p>
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
 * <p>
 * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入："/home/"
 * 输出："/home"
 * 解释：注意，最后一个目录名后面没有斜杠。
 * 示例 2：
 * <p>
 * 输入："/../"
 * 输出："/"
 * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
 * 示例 3：
 * <p>
 * 输入："/home//foo/"
 * 输出："/home/foo"
 * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 * 示例 4：
 * <p>
 * 输入："/a/./b/../../c/"
 * 输出："/c"
 * 示例 5：
 * <p>
 * 输入："/a/../../b/../c//.//"
 * 输出："/c"
 * 示例 6：
 * <p>
 * 输入："/a//b////c/d//././/.."
 * 输出："/a/b/c"
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(simplifyPath("/home/"));
        System.out.println(simplifyPath("/../"));
        System.out.println(simplifyPath("/home//foo/"));
        System.out.println(simplifyPath("/a/./b/../../c/"));
        System.out.println(simplifyPath("/a/../../b/../c//.//"));
        System.out.println(simplifyPath("/a//b////c/d//././/.."));
    }

    /**
     * ./是需要去掉的，//是需要去掉的，x/../是需要去掉的
     *
     * @param path
     * @return
     */
    public static String simplifyPath(String path) {
        if (path.length() == 0) {
            return path;
        }
        StringBuilder sb = new StringBuilder();
        if (path.startsWith("/")) {
            sb.append("/");
        }
        String[] strings = path.split("/");
        String s;
        for (int i = 0; i < strings.length; i++) {
            s = strings[i];
            if ("..".equals(s)) {
                // 需要向上走能置空的，如果找到了，当前也置空
                for (int j = i - 1; j >= 0; j--) {
                    s = strings[j];
                    if (!"".equals(s) && !".".equals(s)) {
                        strings[j] = "";
                        strings[i] = "";
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < strings.length; i++) {
            s = strings[i];
            if (!"".equals(s) && !".".equals(s)) {
                sb.append(s).append("/");
            }
        }
        path = sb.toString();
        // 移除开头
        if (path.startsWith("/../")) {
            path = path.replaceFirst("/../", "/");
        }
        if (path.length() > 1) {
            path = path.substring(0, path.length() - 1);
        }
        return path;
    }

    /**
     * 这个和我最早的用栈的想法很像
     *
     * @param path
     * @return
     */
    public String simplifyPath2(String path) {
        String[] pathArray = path.split("/");
        // 分割后的几种情况 空格说明是多出来的/，.. .与目录
        StringBuilder res = new StringBuilder();
        Deque<String> stack = new ArrayDeque<>();
        for (int i = 0; i < pathArray.length; i++) {
            // 2种情况，栈为空或者栈不为空
            if (pathArray[i].length() == 0 || pathArray[i].equals(".")) continue;
            if (!stack.isEmpty()) {
                if (pathArray[i].equals("..")) {
                    stack.pop();
                } else {
                    stack.push(pathArray[i]);
                }
            } else {
                if (!pathArray[i].equals("..")) stack.push(pathArray[i]);
            }
        }
        if (stack.isEmpty()) return res.append('/').toString();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
            res.insert(0, '/');
        }
        return res.toString();
    }

}
